import java.util.Arrays;

/**
 * 希尔排序
 *
 * @Author: wanqian
 * @Date: 2021/2/1 12:04
 */
public class ShellSort {

    public static int[] arr = {4, 3, 65, 12, 1, -6, 46, 64};

    public static void main(String[] args) {
        int[] arr = new int[1000000];
        for (int i = 0; i < 1000000; i++) {
            arr[i] = (int) (Math.random() * 1000);
        }

//        System.out.println("排序前" + Arrays.toString(arr));
        long start = System.currentTimeMillis();
        shellSortWithMove(arr);
        long end = System.currentTimeMillis();
        System.out.println("耗时" + (end - start) + "毫秒");
//        System.out.println("排序后" + Arrays.toString(arr));
    }

    /**
     * 1. 首先将数组进行分组排序，arr.length /= 2
     * 2. 组内元素通过分为一个有序表和一个无序表的方式，通过交换位置进行排序
     * 3. 逐渐将元素趋于有序
     *
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int temp;
        //gap为间隔或者说分组数
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//            ++count;
            for (int i = gap; i < arr.length; i++) {
                //j从0开始到length-1-gap，for循环length-gap次
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    } else {
                        break;
                    }
                }
            }
        }
    }

    /**
     * 移动法希尔排序
     *
     * @param arr
     */
    public static void shellSortWithMove(int[] arr) {
        int index;
        int temp;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                temp = arr[i];
                index = i - gap;
                while (index >= 0 && arr[index] > temp) {
                    arr[index + gap] = arr[index];
                    index -= gap;
                }
                arr[index + gap] = temp;
            }
//            System.out.println(Arrays.toString(arr));

        }
    }

    /**
     * 希尔2.0
     *
     * @param arr
     */
    public static void shell2(int[] arr) {
        int temp;
        int index;
        int count = 0;
        //gap为间隔或者说分组数
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//            ++count;
            for (int i = 0; i < arr.length - gap; i++) {
                index = i;
                while (index >= 0 && arr[index] > arr[index + gap]) {
                    temp = arr[index];
                    arr[index] = arr[index + gap];
                    arr[index + gap] = temp;
                    index -= gap;
                }
            }
            System.out.println(String.format("第%d次排序: %s", ++count, Arrays.toString(arr)));
        }
    }
}

